// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-28 19:59
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

import java.util.Collections;
import java.util.List;

public class IncreasingTriplet {
    // 递增的三元子序列
    // nums[i]左边的最小值应该小于nums[i]，右边的最大值应该大于nums[i]
    // 遍历数组并且记录当前位置左边最小值和右边最大值 leftMin && rightMax
    public boolean increasingTriplet(int[] nums) {
        int len = nums.length;
        int[] leftMin = new int[len];
        int[] rightMax = new int[len];
        int j = len - 1;
        leftMin[0] = nums[0];
        rightMax[j] = nums[j];
        --j;

        for (int k = 1; k < nums.length; k++) {
            leftMin[k] = Math.min(nums[k], leftMin[k - 1]);
            rightMax[j] = Math.max(nums[j], rightMax[j + 1]);
            --j;
        }
        for (int k = 0; k < nums.length; k++) {
            if (nums[k] > leftMin[k] && nums[k] < rightMax[k]) { // 存在三元组的充要条件
                return true;
            }
        }
        return false;
    }

    @Test
    public void shout00() {
        int[] test = {5, 9, 6, 8};
        System.out.println(increasingTriplet(test));
    }

}
